home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Advanced I⁄O v2.3 / Advanced i⁄o / arithm.h < prev    next >
Text File  |  1995-05-29  |  7KB  |  217 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3.  ************************************************************************
  4.  *
  5.  *                   Arithmetic Coding
  6.  *
  7.  * The present package provides a set of functions that are intended to be
  8.  * used for lossless coding of a sequence of integers with optimal
  9.  * variable-bit code. The package allows one to treat a new or 
  10.  * already opened file as a bit stream that integer data can be read/written
  11.  * to/from.
  12.  *
  13.  * The present implemention is based on the algorithm thoroughly
  14.  * explained in
  15.  *    Text Compression
  16.  *    T.C.Bell, J.G.Cleary, I.H.Witten
  17.  *    Prentice Hall, Englewood Cliffs, NJ (c)1990
  18.  *    Chap. 5 pp.100-140
  19.  *
  20.  * The present files declares two classes, Input_Data_Model and 
  21.  * ArithmCoding. The former is responsible for providing the codec
  22.  * with the probabilities (frequencies) a given data item is expected
  23.  * to appear with, and for finding a symbol given its cumulative frequency.
  24.  * Input_Data_Model may also modify the model to account for a new symbol. 
  25.  * ArithmCoding class is a sort of the 'iostream' class that writes/reads
  26.  * data item to/from the stream performing coding/encoding. It relies on 
  27.  * the Input_Data_Model for the probabilities needed to perform the
  28.  * arithmetic coding.
  29.  *
  30.  * $Id: arithm.h,v 2.0 1995/02/07 19:39:15 oleg Exp oleg $
  31.  *
  32.  ************************************************************************
  33.  */
  34.  
  35. #ifndef __GNUC__
  36. #pragma once
  37. #endif
  38.  
  39. #ifndef _arithm_h
  40. #define _arithm_h
  41.  
  42. #ifdef __GNUC__
  43. #pragma interface
  44. #endif
  45.  
  46. #include "myenv.h"
  47. #include "endian_io.h"
  48.  
  49. /*
  50.  *------------------------------------------------------------------------
  51.  *            Class Arithmetic Coding
  52.  *
  53.  * Note the meaning of the following constant parameters and constraints
  54.  * Top_value = 2^Code_size - 1        Max value of the codeword
  55.  * (Top_value+1)*Top_freq         should fit into the word length
  56.  *                    available
  57.  * In other words, the following relation should hold
  58.  *    Freq_size <= Code_size - 2
  59.  *    Freq_size + Code_size <= int arithm precision (during 
  60.  *                              scaling the interval)
  61.  * where 2^Freq_size-1 is the top value for the cumulative frequency.
  62.  *
  63.  * The present program uses
  64.  *    17-bit codeword, Code_size = 17, Top_value = 2^17-1
  65.  *    freq_size = 15,  Top_freq  = 2^15-1
  66.  * It implies 32-bit precision arithmetics (long unsigned int) must be used
  67.  * during the code scaling to avoid overflows
  68.  */
  69.  
  70. typedef signed short Symbol;    // Type of the data to code
  71. typedef unsigned short Index;    // Type of the transformed data
  72. typedef unsigned long Lword;
  73.  
  74.                 // This is a generic (base) class for any
  75.                 // model of input data. It declares the
  76.                 // interface to the Arithmetic coder and
  77.                 // sets the required basics. Any derived
  78.                 // class (ie particular model of input)
  79.                 // may expand it.
  80. class Input_Data_Model
  81. {
  82.  
  83. protected:
  84.  
  85.   Lword Top_freq;        // The top value for the frequency
  86.   Index EOF_index;        // Index of the EOF symbol
  87.  
  88.   int    no_indices;        // No. of indices
  89.  
  90.   Lword * frequencies;        // Ordered table of frequencies
  91.   Lword * cum_frequencies;    // Cumulative frequencies, 
  92.                 // cum_freq[no_indices] = freq[no_indices]
  93.                 // cum_freq[i-1] = cum_freq[i] + freq[i]
  94.                 // cum_freq[0] = total frequency count
  95.  
  96.                     // Construct a model for a given
  97.                     // number of symbols
  98.   Input_Data_Model(void);
  99.   virtual ~Input_Data_Model(void);
  100.   void allocate_model(const int no_symbols);
  101.  
  102. public:            // The following describes the interface that
  103.             // is required by the arithmetic coder.
  104.  
  105.                     // Set the Top_freq that is
  106.                     // required by coder
  107.   void agree_on_top_freq(const int top_freq);
  108.  
  109.                     // Prepare the input model,
  110.                     // write out/read in model parameters
  111.                     // if necessary.
  112.   virtual void open(BitIn& file) = 0;            // for reading
  113.   virtual void open(BitOut& file) = 0;            // for writing
  114.  
  115.                     // Update the adaptive model
  116.   virtual void update_model(const Index index) = 0;
  117.  
  118.                     // We expect that the source statistics
  119.                     // is going to change, so we need to
  120.                     // put less emphasis on the past
  121.                     // statistics accumulated by an
  122.                     // adaptive model 
  123.   virtual void scale_down_past(void) = 0;
  124.  
  125.                     // Return the index of a symbol
  126.   virtual Index  get_index(const Symbol symbol) const = 0;
  127.                     // and the symbol for an index
  128.   virtual Symbol get_symbol(const Index index) const = 0;
  129.                     // Find an index given its cum freq
  130.   Index  find_index(const Lword cum_fr) const;
  131.  
  132.   Lword total_cum_freq() const    { return cum_frequencies[0]; }
  133.   Lword cum_freq(const Index index)  const 
  134.                   { return cum_frequencies[index]; }
  135.   Lword freq(const Index index) const    
  136.                 { return cum_frequencies[index-1] - 
  137.                          cum_frequencies[index]; }
  138.  
  139.   Index eof_index() const    { return EOF_index; }
  140. };
  141.  
  142.  
  143. class ArithmCodingData
  144. {
  145. protected:
  146.   typedef unsigned long int Code;
  147.  
  148.                 // Coding constants 
  149.   enum { Code_size = 17 };        // Size of the codeword
  150.   enum { Top_value  = (1<<Code_size)-1 };
  151.   enum { First_qtr = Top_value/4+1 };    // Point after the first quarter
  152.   enum { Half      = 2*First_qtr,    // Point after the first half
  153.        Third_qtr = 3*First_qtr };    // Point after the third quarter
  154.  
  155.   Input_Data_Model& Source_model;
  156.  
  157.                 // Current state of encoding/decoding
  158.   Code low, high;            // Ends of the current code region
  159.   Code bits_to_follow;            // No. of opposite bits to output
  160.                     // after the next bit
  161.   Code value;                // Currently seen code value during
  162.                     // decoding
  163.  
  164.   enum Status { Init, Coding, EoF } Coding_status;
  165. public:
  166.   ArithmCodingData(Input_Data_Model& model);
  167. };
  168.  
  169. class ArithmCodingOut : ArithmCodingData, public BitOut
  170. {
  171.   void initialize(void);
  172.   void encode_index(const Index index);    // Do actual encoding
  173.   void done_encoding(void);
  174.  
  175.   void put_bit_plus_follow(const char bit); // Output a bit following by
  176.                     // bits_to_follow opposite bits
  177.  
  178. public:
  179.                     // Construct the code stream for
  180.                     // a given model of input data
  181.   ArithmCodingOut(Input_Data_Model& model) : ArithmCodingData(model) {}
  182.   ~ArithmCodingOut(void)            { close(); }
  183.  
  184.                       // Open the coded stream
  185.   void open(const char * file_name)
  186.         { BitOut::open(file_name); initialize(); }
  187.   void open(EndianOut& file)
  188.         { BitOut::share_with(file); initialize(); }
  189.  
  190.   void close(void);            // Close the coded stream
  191.  
  192.   void put(const Symbol symbol);    // Write a symbol into the coded stream
  193. };
  194.  
  195.  
  196. class ArithmCodingIn : ArithmCodingData, public BitIn
  197. {
  198.   void initialize(void);
  199.   Index decode_index();            // Do actual decoding
  200.  
  201. public:
  202.   ArithmCodingIn(Input_Data_Model& model) : ArithmCodingData(model) {}
  203.   ~ArithmCodingIn(void)            { close(); }
  204.  
  205.                       // Open the coded stream
  206.   void open(const char * file_name)
  207.         { BitIn::open(file_name); initialize(); }
  208.   void open(EndianIn& file)
  209.         { BitIn::share_with(file); initialize(); }
  210.  
  211.   void close(void);            // Close the coded stream
  212.  
  213.   Symbol get();                // Get a symbol from the coded stream
  214.   bool is_eof(void) const        { return Coding_status == EoF; }
  215. };
  216. #endif
  217.